package a09_贪心算法;

//摆动序列：相邻元素差值一正一负
//删除元素后，最长的摆动序列
//[3,4]的摆动为2
//把单调坡上的元素删除掉

//没必要删除元素，我们只需要遇到转折result++

//如何判断是摆动
//某个点的前一个点和后一个点
//prediff = nums[i] - nums[i-1]
//currdiff = nums[i+1] - nums[i]

//上下坡有平坡
//[1,2,2,2,1]
//[1,2,1]
// prediff >= 0 && currdiff < 0
// prediff < 0 && currdiff >= 0


//首尾元素 都要算坡度
//如果数组里面有2个元素，无法计算prediff和currdiff
//[1,2] 左边的话我们在前面加一个1[1,1,2]
//右边默认有一个摆动，所以result从1开始

//情况3：单调坡有平坡
//[1,1,2,2,3,3,4,4,5,5,6,6]
//那么每次从平到起都会result+1，此时preDiff=0，currDiff=1
//  [  1,  1,  2,  2,  3,  3  ]
//    0  0   1    0   1   0
//     x   √    x   √   x
//    0  0   1    0   1   0
//    0  0   1    1   1   0
//
// prevDiff = 0 && currDiff > 0咋们也result++了
public class a03_摆动序列 {

    public static void main(String[] args) {
        a03_摆动序列 test = new a03_摆动序列();
        int i = test.wiggleMaxLength(new int[]{1, 1, 2, 2, 3, 3});
        System.out.println(i);
    }

    //首先我们是在之前是平的，突然上升和下降才算转折，而不是在之前是上升的，突然变平当转折的
    //如果先平后升再平再升再平再升，那么就相当于转折了三次了
    //为了防止上面的问题，我们可以这样做：
    //第一次平升转折点算一次，此时更新下次的prevDiff，
    //正常来说后面的转折点prevDiff=0，currDiff=2，但是我们上次转折后更新prevDiff后，就没更新过prevDiff，所以一直是>0的
    public int wiggleMaxLength(int[] nums) {
        int result = 1;
        int currentIdx = 0;

        int prevDiff = 0;
        while (currentIdx < nums.length - 1) {
            int currDiff = nums[currentIdx + 1] - nums[currentIdx];
            System.out.println("prevDiff = " + prevDiff);
            System.out.println("currDiff = " + currDiff);
            System.out.println();
            if ((prevDiff <= 0 && currDiff > 0) || (prevDiff >= 0 && currDiff < 0)) {
                result++;
                prevDiff = currDiff;
            }
            currentIdx++;
        }
        return result;
    }
}
